package com.LeetCode.List;

import org.junit.Test;

/**
 * 交换链表奇偶位置节点
 *
 * 奇偶链表
 */
public class oddEvenList {

    public ListNode oddEvenList2(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p1 = dummy, p2 = dummy.next;
        while(p2 != null && p2.next !=null){
            p1.next = p2.next;
            p2.next = p1.next.next;
            p1.next.next = p2;
            p1 = p2;
            p2 = p2.next;
        }

        return dummy.next;
    }


    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // head 为奇链表头结点，o 为奇链表尾节点
        ListNode o = head;
        // p 为偶链表头结点
        ListNode p = head.next;
        // 将偶数链表的头结点存起来，因为一会遍历会丢失
        ListNode e = p;
        while (o.next != null && e.next != null) {
            o.next = e.next;
            o = o.next;
            e.next = o.next;
            e = e.next;
        }
        o.next = p;
        return head;

    }


    @Test
    public void test(){
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        ListNode.printList(node1);
        ListNode.printList(oddEvenList(node1));
    }
}
